#include<iostream>
#include <string>
#include<queue>
#include <stack>
using namespace std;
class Edge {
public:
	Edge() {
		this->begin = "";
		this->letter = ' ';
		this->end = "";
	};
	Edge(string begin, char letter, string end) {
		this->begin = begin;
		this->letter = letter;
		this->end = end;
	}
	void setletter(char ch) {
		this->letter = ch;
	}
	char getletter() {
		return this->letter;
	}
	void setBegin(string ch) {
		this->begin = ch;
	}
	string getBegin() {
		return this->begin;
	}
	void setEnd(string ch) {
		this->end = ch;
	}
	string getEnd() {
		return this->end;
	}
public:
	char letter;
	string begin;
	string end;

};
class nfa{
public:
	queue<Edge> NfaEdge; // all edge
	stack<Edge> st; //begin and end state
	int StateNum; //state number
public:
   nfa() {
		this->StateNum=0;
	};
   //a|b 
   void create_nfa_alternation() {
   	Edge ed1(this->st.top());
   	this->st.pop();
   	Edge ed2(this->st.top());
   	this->st.pop();
	Edge newed1(to_string(StateNum), '#', ed1.getBegin());
	Edge newed2(to_string(StateNum), '#', ed2.getBegin());
	Edge newed3(ed1.getEnd(), '#', to_string(StateNum + 1));
	Edge newed4(ed2.getEnd(), '#', to_string(StateNum + 1));
	this->NfaEdge.push(newed1);
	this->NfaEdge.push(newed2);
	this->NfaEdge.push(newed3);
	this->NfaEdge.push(newed4);
	Edge end(to_string(StateNum), ' ', to_string(StateNum + 1));
	StateNum= StateNum + 2;
   	this->st.push(end);
   }
   //a.b
   void create_nfa_concatenation() {
   	Edge ed1 = this->st.top();
   	this->st.pop();
   	Edge ed2 = this->st.top();
   	this->st.pop();
	Edge newed1(ed2.getEnd(), '#', ed1.getBegin());
	this->NfaEdge.push(newed1);
	Edge end(ed2.getBegin(), ' ', ed1.getEnd());
   	this->st.push(end);
   }
   //a*
   void create_nfa_closure() {
   	Edge ed = this->st.top();
   	this->st.pop();
	Edge ed1(to_string(StateNum), '#', ed.getBegin());
	Edge ed2(to_string(StateNum), '#', to_string(StateNum + 1));
	Edge ed3(ed.getEnd(), '#', ed.getBegin());
	Edge ed4(ed.getEnd(), '#', to_string(StateNum + 1));
	this->NfaEdge.push(ed1);
	this->NfaEdge.push(ed2);
	this->NfaEdge.push(ed3);
	this->NfaEdge.push(ed4);
	Edge end(to_string(StateNum), ' ', to_string(StateNum + 1));
	StateNum = StateNum + 2;
   	this->st.push(end);
   }
   //a
   void create_nfa_atom(char c) {
	Edge ed1(to_string(StateNum), c, to_string(StateNum + 1));
	this->NfaEdge.push(ed1);
	Edge end(to_string(StateNum), ' ', to_string(StateNum + 1));
	StateNum = StateNum + 2;
   	this->st.push(end);
   }
    //print
   void PrintNfa() {
   	cout<<"NFA:"<<endl;
    	int queue_size = this->NfaEdge.size();
      	for(int i = 0; i < queue_size; i++) {   
      	Edge e = this->NfaEdge.front();
      	cout << e.getBegin() << 
    	" " << e.getletter() << " " << e.getEnd() << endl;
      	this->NfaEdge.push(this->NfaEdge.front());
      	this->NfaEdge.pop(); 
    }
  }  
};

